package leetcode;

public class MergeKList {

    class ListNode{
        int  val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode mergeKList(ListNode[] lists){
        ListNode preHead = new ListNode(0);
        ListNode root = preHead;
        while (true){
            ListNode minNode = null;
            int minIndex = 0;
            for(int i = 0; i < lists.length; i++){
                ListNode item = lists[i];
                if(item != null){
                    if(minNode == null){
                        minNode = item;
                        minIndex = i;
                    }else{
                        if(item.val < minNode.val){
                            minNode = item;
                            minIndex = i;
                        }
                    }
                }
            }
            if(minNode == null){
                break;
            }else{
                root.next = minNode;
                root = root.next;
                lists[minIndex] = lists[minIndex].next;
            }
        }
        return preHead.next;
    }

}
